/**
 * It was proposed by Christian Goldbach that every odd composite number can 
 * be written as the sum of a prime and twice a square.
 *
 *  9 = 7  + 2*1^2
 * 15 = 7  + 2*2^2
 * 21 = 3  + 2*3^2
 * 25 = 7  + 2*3^2
 * 27 = 19 + 2*2^2
 * 33 = 31 + 2*1^2
 *
 * It turns out that the conjecture was false.
 * 
 * What is the smallest odd composite that cannot be written as the sum of a 
 * prime and twice a square?
 *
 * ANSWER: 5777
 */

#include <iostream>
#include <cmath>
#include "prime.h"

void solve_problem_46()
{
	const int N = 1000000;
	prime_numbers primes(N);

	// For each odd composite number below N, try decompose it into the sum
	// of a prime and twice a square.
	for (int n = 9; n < N; n += 2)
	{
		// skip prime number itself
		if (primes.test(n))
			continue;

		// test each possible square number
		bool found = false;
		for (int b = (int)sqrt((double)(n-3)/2); b >= 1; b--)
		{
			int a = n - 2*b*b;
			if (primes.test(a)) 
			{
				found = true;
				break;
			}
		}
		if (!found)
		{
			//cout << "First non-conforming number is " << n << endl;
			std::cout << n << std::endl;
			break;
		}
	}
}


